//================v1要点总结===============
/**
 * 1.DFS 判断条件太过复杂，而且容易死循环
 * 2.本方法采用动态规划的思想，状态转移方程为：
 * 
 * f(i,j) = 1 + min( f(i,j+1), f(i,j-1), f(i-1,j), f(i+1,j) )      当f(i,j) = 1
 * f(i,j) = 0                                                       当f(i,j) = 0
 * 
 * 3. node 还不认识^符号，老老实实写Math.pow
 */


/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {

    let r = mat.length
    let c = mat[0].length
    let rsltMat = []

    // 初始化数据
    for (let ri = 0; ri < r; ri++) {
        let tempRow = []
        for (let ci = 0; ci < c; ci++) {
            tempRow.push(mat[ri][ci] ? 10000 * 2 : 0)
        }
        rsltMat.push(tempRow)
    }

    // 下面的比较思想为：
    // 各个方向，前一个元素为当前的最小值，因此当前元素的值 = min(前一个元素的值+1,当前值比较)

    // 从左上角往右下角移动
    for (let ri = 0; ri < r; ri++) {
        for (let ci = 0; ci < c; ci++) {
            if (ri - 1 >= 0) {
                //  纵向向下移动
                rsltMat[ri][ci] = Math.min(rsltMat[ri][ci], rsltMat[ri - 1][ci] + 1)
            }
            if (ci - 1 >= 0) {
                // 横向向右移动
                rsltMat[ri][ci] = Math.min(rsltMat[ri][ci], rsltMat[ri][ci - 1] + 1)
            }
        }
    }

    // 从右下角往左上角移动
    for (let ri = r - 1; ri >= 0; ri--) {
        for (let ci = c - 1; ci >= 0; ci--) {
            if (ri + 1 < r) {
                // 纵向向上移动
                rsltMat[ri][ci] = Math.min(rsltMat[ri][ci], rsltMat[ri + 1][ci] + 1)
            }

            if (ci + 1 < c) {
                // 横向向下移动
                rsltMat[ri][ci] = Math.min(rsltMat[ri][ci], rsltMat[ri][ci + 1] + 1)
            }
        }
    }
    // 至此，四个方向的值都比较过，并取得了四个值的最小值，得到最终结果
    return rsltMat
};

console.log(updateMatrix([
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
    [0, 0, 0]]))

// console.log(updateMatrix([
//     [1, 1, 1],
//     [1, 0, 1],
//     [1, 1, 1],
//     [1, 1, 1]]))


